package leetcode101_xqzhao

// TODO 颜色分类 【-】 脑筋急转弯 | 双指针

func sortColors(nums []int) {
	n := len(nums)
	left, right := 0, n-1 // left: 红色  right: 蓝色

	for i := 0; i <= right; {
		// 如果扫描到 0, 则其左边已经全是 0 和 1 了, 所以交换之后 i 位置一定是 1, 可以直接 i++
		if nums[i] == 0 {
			nums[i], nums[left] = nums[left], nums[i]
			left++
			i++
		} else if nums[i] == 2 {
			nums[i], nums[right] = nums[right], nums[i]
			right--
		} else {
			i++
		}
	}
}
